package co.moyueheng;


import org.w3c.dom.Node;

import javax.swing.*;
import java.security.cert.TrustAnchor;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;

public class BinarySearchTree<E> {
    private int size;
    private Node<E> root;
    private Comparator<E> comparator;

    public BinarySearchTree() { // compareable这种方法，比较器是空的
        this(null);
    }


    public BinarySearchTree(Comparator<E> comparator) {
        this.comparator = comparator;
    }

    // 后序遍历
    public void postorderTraversal() {
        this.postorderTraversal(root);
    }

    // 后序遍历， 先子节点后父节点的遍历方式
    private void postorderTraversal(Node<E> node) {
        if (node == null) {
            return;
        }
        this.inorderTraversal(node.left);
        this.inorderTraversal(node.right);
        System.out.println(node.element);
    }

    // 中序遍历
    public void inorderTraversal() {
        this.inorderTraversal(this.root);
    }

    // 中序遍历， 可以在按照升序或者降序的方式展示
    private void inorderTraversal(Node<E> node) {
        if (node == null) {
            return;
        }
        this.inorderTraversal(node.left);
        System.out.println(node.element);
        this.inorderTraversal(node.right);
    }

    // 前序遍历
    public void preorderTraversal() {
        this.preorderTraversal(this.root);
    }

    // 前序遍历
    private void preorderTraversal(Node<E> node) {
        if (node == null) {
            return;
        }
        System.out.println(node.element);
        this.preorderTraversal(node.left);
        this.preorderTraversal(node.right);
    }

    // 层序遍历，
    public void evelOrderTranversal() {
        if (this.root == null) {
            return;
        }
        Queue<Node<E>> queue = new LinkedList<Node<E>>();
        queue.offer(this.root);
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            System.out.println(node.element);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }


    // 层序遍历， 翻转二叉树
    public void invert() {
        if (this.root == null) {
            return;
        }
        Queue<Node<E>> queue = new LinkedList<Node<E>>();
        queue.offer(this.root);
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            // 操作
            Node<E> temp;
            temp = node.left;
            node.left = node.right;
            node.right = temp;

//            System.out.println(node.element);


            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }

    // 前驱节点
    public Node<E> predocessor(Node<E> node) {
        if (node == null) return null;
        Node<E> p = node.left;
        // 说明前驱节点在左子树当中， left.right.right.right
        if (p != null) {
            // 在左子树里面找前驱
            while (p.right != null) {
                p = p.right;
            }
            return p;
        }
        // 说明前驱节点在祖父节点当中， parent.parent.parent.parent， 直到是自己不是parent的左节点
        while (p.parent != null && p == p.parent.left) {
            p = p.parent;
        }
        if (p.parent == null) return null; // p.parent == null
        return p; //  p = p.parent.right
    }

    // 后继节点
    public Node<E> successor(Node<E> node) {
        if (node == null) return null;

        Node<E> s = node.right;
        // 说明前驱节点在左子树当中， right.left.left.left
        if (s != null) {
            // 在左子树里面找前驱
            while (s.left != null) {
                s = s.left;
            }
            return s;
        }
        // 说明前驱节点在祖父节点当中， parent.parent.parent.parent， 直到是自己不是parent的左节点
        while (s.parent != null && s == s.parent.right) {
            s = s.parent;
        }
        if (s.parent == null) return null; // p.parent == null
        return s; //  s = s.parent.left
    }

    // 层序遍历,有分层展示
    public void showTree() {
        if (root == null) {
            return;
        }
        Node<E> node;
        Queue<Node<E>> queue = new LinkedList<Node<E>>(); // 下一层的节点
        Queue<Node<E>> temp_queue = new LinkedList<Node<E>>(); // 当前层的节点
        queue.offer(this.root);


        while (!queue.isEmpty()) {
            // temp_queue.addAll(queue);
            // temp_queue
            // 全部弹出
            while (!queue.isEmpty()) {
                temp_queue.add(queue.poll());
            }

            while (!temp_queue.isEmpty()) {
                node = temp_queue.poll();
                System.out.print(node.element.toString() + "  ");
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            System.out.println();
        }
    }

    // 返回二叉树的高度, 递归形式
    public int height() {
        return this.height(this.root);
    }

    private int height(Node<E> node) {
        if (node == null) return 0;
        return 1 + Math.max(this.height(node.left), height(node.right));
    }

    // 返回二叉树的高度, 层序遍历
    public int height2() {
        if (this.root == null) {
            return 0;
        }
        int height = 0;
        int levelSize = 1;

        Queue<Node<E>> queue = new LinkedList<Node<E>>();
        queue.offer(this.root);

        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            levelSize--;
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
            if (levelSize == 0) { // 监听状态， 判断这层有没有遍历完，然后更新状态
                height++;
                levelSize = queue.size();
            }
        }

        return height;
    }

    // 判断一棵树算不算完全二叉树
    public boolean isComplete() {
        if (root == null) return false;

        // 标记后面是否应该全为叶子节点
        boolean isLeafLater = false;

        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(this.root);

        while (!queue.isEmpty()) {

            Node<E> node = queue.poll();
            if (isLeafLater && !node.isLeaf()) return false;

            // 先把该添加的都添加进去， 然后再分类，
            if (node.left != null) {
                queue.offer(node.left);
            } else if (node.right != null) {
                return false;
            }

            if (node.right != null) {
                queue.offer(node.right);
            } else {
                isLeafLater = true;
            }
        }

        return true;

    }

    // 打印数状结构
    public String toString() {
        StringBuilder sb = new StringBuilder();
        this.toString(this.root, sb, "");
        return sb.toString();
    }

    private void toString(Node<E> node, StringBuilder sb, String prefix) {
        if (node == null) {
            return;
        }
        this.toString(node.right, sb, prefix + "[R]");
        sb.append(prefix).append(node.element).append("\n");
        this.toString(node.left, sb, prefix + "[L]"); // 告诉他你是左还是右边

    }


    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return this.size == 0;
    }

    public void clear() {
        this.size = 0;
    }

    public void add(E element) {
        if (this.root == null) {
            this.root = new Node<E>(element, null);
            this.size++;
            return;
        }
        // 1.找到父节点和方向
        Node<E> parent = root;
        int cmp = 0;

        Node<E> node = root;
        while (node != null) {
            cmp = this.compare(element, node.element);
            parent = node;
            if (cmp > 0) {
                node = node.right;
            } else if (cmp < 0) {
                node = node.left;
            } else { // 如果相等什么都不做
                return;
            }
        }

        // 2.将新节点放上去
        Node<E> newNode = new Node<E>(element, parent);
        if (cmp > 0) {
            parent.right = newNode;
        } else {
            parent.left = newNode;
        }
        this.size++;
    }

    // 删除某个元素
    public void remove(E element) {
        this.remove(this.getNode(element));
    }

    //  根据元素获得节点
    private Node<E> getNode(E element) {
        Node<E> node = root;
        // 搜索
        while (node != null) {
            int cmp = this.compare(element, node.element);
            if (cmp == 0) return node; // 找到
            if (cmp > 0) {
                node = node.right;
            } else {
                node = node.left;
            }
        }
        // 没找到
        return null;
    }

    // 删除某个节点
    private void remove(Node<E> node) {
        if (node == null) return;
        size--;

        // 度为2
        if (node.hasTwoChildren()) {
            Node<E> sNode = this.successor(node); // 拿后继节点， 前驱节点一定是度为0的或者度为1的
            // 后继节点覆盖
            node.element = sNode.element;
            // 删除后继节点
            node = sNode; // 现在让node也指向了度为1和度为0的节点， 后面统一删除node
            // 用
        }

        // 删除node节点（node的度必然为1或者0）
        Node<E> replacement = node.left != null ? node.left : node.right; // replacement就是被删除节点的子节点
        if (replacement != null) {// 度为1
            replacement.parent = node.parent;
            if (node.parent == null) { // node == root
                root = replacement;
                replacement.parent = null; //
            } else if (node == node.parent.left) {
                node.parent.left = replacement;
            } else {
                node.parent.right = replacement;
            }
        } else {// 度为0
            if (node.parent == null) { // node == root, 根节点是叶子节点
                this.root = null;
            } else {
                if (node == node.parent.left) {
                    node.parent.left = null;
                } else {
                    node.parent.right = null;
                }
            }
        }
    }

    boolean contains(E element) {
        return false;
    }

    // 如果 <0 e1 < e2, 如果 > 2 e1 > e2, 如果 =0 e1 = e2
    private int compare(E e1, E e2) {
        if (comparator != null) {
            return this.comparator.compare(e1, e2);
        }
        return ((Comparable<E>) e1).compareTo(e2); // 强转失败也就是说他自身不是可比较的，也就是说即没有传比较器自身也不可比较
    }

    //    树的节点元素不能为空
    private void elementNotNullCheck(E element) {
        if (element == null) {
            throw new IllegalArgumentException("element不能为空");
        }
    }

    private static class Node<E> {
        E element;
        Node<E> left;
        Node<E> right;
        Node<E> parent;

        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }

        public boolean isLeaf() {
            return this.left == null && this.right == null;
        }

        public boolean hasTwoChildren() {
            return this.left != null && this.right != null;
        }
    }
}
